package 高频题;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class 考场就座_855 {
    class ExamRoom {
        private Map<Integer, int[]> startMap;
        private Map<Integer, int[]> endMap;
        private TreeSet<int[]> pq;
        private int N;

        /**
         * 构造函数，传入座位总数N
         *
         * @param N
         */
        public ExamRoom(int N) {
            this.N = N;
            startMap = new HashMap<>();
            endMap = new HashMap<>();
            pq = new TreeSet<int[]>((a, b) -> {
                //算出两个线段的长度
                int disA = distance(a);
                int disB = distance(b);
                //如果长度相同就比较索引
                if (disA == disB) {
                    return b[0] - a[0];
                }
                return disA - disB;
            });
            //在有序集合中先放一个虚拟线段
            addInterval(new int[]{-1, N});
        }

        /**
         * 来一名考生，返回你给他分配的座位
         *
         * @return
         */
        public int seat() {
            // 从有序集合中取出最长的线段
            int[] longest = pq.last();
            int x = longest[0];
            int y = longest[1];

            int seat;
            if (x == -1) {
                seat = 0;
            } else if (y == N) {
                seat = N - 1;
            } else {
                seat = (y - x) / 2 + x;
            }

            // 将最长的线段分成两段
            int[] left = new int[]{x, seat};
            int[] right = new int[]{seat, y};

            removeInterval(longest);
            addInterval(left);
            addInterval(right);

            return seat;
        }

        /**
         * 坐在p位置的考生离开了
         *
         * @param p
         */
        public void leave(int p) {
            // 将p为左右的线段找出来
            int[] right = startMap.get(p);
            int[] left = endMap.get(p);

            // 合并两个线段成为一个
            int[] merged = new int[]{left[0], right[1]};

            removeInterval(left);
            removeInterval(right);
            addInterval(merged);
        }


        /*一些需要用到的API*/

        //去除线段
        private void removeInterval(int[] intv) {
            pq.remove(intv);
            startMap.remove(intv[0]);
            endMap.remove(intv[1]);
        }

        //        增加线段
        private void addInterval(int[] intv) {
            pq.add(intv);
            startMap.put(intv[0], intv);
            endMap.put(intv[1], intv);
        }

        //        计算线段的长度
        private int distance(int[] intv) {
            int x = intv[0];
            int y = intv[1];
            if (x == -1) {
                return y;
            }
            if (y == N) {
                return N - x - 1;
            }

            //中点和端点之间的长度
            return (y - x) / 2;
        }
    }
}
